public class QuickSort {

    public static void main(String[] args) {


        int array[] = {-4, 2, 10, 9, 8, 7, 6};
        quickSort(array, 0, array.length - 1);
        int K = 3;
        System.out.println(String.format("第%d小的数为:%d", K, array[K - 1]));
    }


    public static void quickSort(int[] array, int l, int r) {

        if (l >= r) {
            return;
        }
        //左
        int i = l;
        //右
        int j = r;
        //基线数
        int x = array[i];

        while (i < j) {
            //右到左找到小于基数的元素
            while (i < j && array[j] >= x) {
                j--;
            }
            if (i < j) {
                array[i] = array[j];
                i++;
            }
            //左到右找到大于等于基数的元素
            while (i < j && array[i] < x) {
                i++;
            }
            if (i < j) {
                array[j] = array[i];
                j--;
            }
        }
        //排完时放基数
        array[i] = x;
        //基数左边和右边再排
        quickSort(array, l, i);
        quickSort(array, i + 1, r);
    }
}
